package com.hdu.hot100.heap;


import java.util.Random;


public class lc215 {



    class Solution {
        static Random random = new Random();
        int ans;

        public int findKthLargest(int[] nums, int k)
        {
            quickSort(nums, 0, nums.length - 1, nums.length - k);
            return ans;
        }

        void quickSort(int[] nums, int l, int r, int kth)
        {
            if (r >= l)
            {
                int partitionIndex = partition(nums, l, r);
                if (kth == partitionIndex)
                {
                    ans = nums[partitionIndex];
                    return;
                }
                else if (kth < partitionIndex)
                {
                    quickSort(nums, l, partitionIndex - 1, kth);
                }
                else
                {
                    quickSort(nums, partitionIndex + 1, r, kth);
                }
            }
        }

        int partition(int[] nums, int l, int r)
        {
            int randomIndex = random.nextInt(r - l + 1) + l;
            int pivot = nums[randomIndex];
            swap(nums, l, randomIndex);
            int left = l;
            int right = r;
            while (left < right)
            {
                while (left < right && nums[right] >= pivot) right--;
                while (left < right && nums[left] <= pivot) left++;
                if (left == right) break;
                swap(nums, left, right);
            }
            swap(nums, l, right);
            return right;
        }


        void swap(int[] nums, int l, int r)
        {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
    }
}

